import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 591. 标签验证器
 * https://leetcode-cn.com/problems/tag-validator/
 */
public class Solutions_591 {
    public static void main(String[] args) {
//        String code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>";  // output: true
//        String code = "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>";  // output: true
//        String code = "<A>  <B> </A>   </B>";  // output: false
//        String code = "<DIV>  div tag is not closed  <DIV>";  // output: false
//        String code = "<DIV>  unmatched <  </DIV>";  // output: false
//        String code = "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>";  // output: false
//        String code = "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>";  // output: false
//        String code = "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>";  // output: false
//        String code = "<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>";  // output: false   ![CDATA[]] 未包含在标签中
//        String code = "<A></A><B></B>";  // output: false
        String code = "<A><![CDATA[</A>]]>!!!!!</A>";  // output: true

        boolean result = isValid(code);
        System.out.println(result);
    }

    /**
     * 关键：只有出现 '<' 和 '!' 字符时，需要判断，出现 '>' 和 ']' 字符时，不需要判断
     */
    public static boolean isValid(String code) {
        if (code == null || code.length() < 7) {
            // <A></A>，合法标签，最少需要 7 个字符
            return false;
        }
        char[] arr = code.toCharArray();
        Deque<String> stack = new ArrayDeque<>();
        int len = arr.length;

        StringBuilder sb = null;
        if (arr[0] != '<' || arr[len - 1] != '>') {
            return false;
        }
        int i = 0;
        while (i < len) {
            if (arr[i] == '<') {
                // 解析起始标签
                i ++;
                boolean isEnd = false;
                // 可能是起始标签，也可能是闭合标签 '</'
                if (i < len && arr[i] == '/') {
                    i ++;
                    isEnd = true;
                } else if (arr[i] == '!') {
                    if (stack.isEmpty()) {
                        // ![CDATA[]] 必须包含在标签中
                        return false;
                    }
                    // <![CDATA[ 结构，那么查找下一个 ]]>
                    int endIdx = code.indexOf("]]>", i);
                    if (endIdx == -1) {
                        return false;
                    }
                    // 截取出 [CDATA[...]] 字符片段
                    String cdata = code.substring(i, endIdx);
                    if (!cdata.startsWith("![CDATA[")) {
                        return false;
                    }
                    i = endIdx + 3;
                    continue;
                }
                sb = new StringBuilder();
                // 解析得到标签名称，遍历找到下一个 '>'
                while (i < len && arr[i] != '>') {
                    // 合法的 TAG_NAME 仅含有大写字母，长度在范围 [1,9] 之间
                    if (arr[i] < 'A' || arr[i] > 'Z') {
                        return false;
                    }
                    sb.append(arr[i]);
                    if (sb.length() > 9) {
                        return false;
                    }
                    i ++;
                }
                if (sb.length() < 1) {
                    // 标签名称长度最短为 1
                    return false;
                }
                String tag = sb.toString();
                if (isEnd) {
                    // 栈顶元素（起始标签）出栈，并判断是否对应
                    if (stack.isEmpty()) {
                        return false;
                    }
                    String startTag = stack.pop();
                    if (!startTag.equals(tag)) {
                        // "<A>  <B> </A>   </B>" 的情况
                        return false;
                    }
                    if (stack.isEmpty() && i != arr.length - 1) {
                        // "<A></A><B></B>" 的情况
                        return false;
                    }
                } else {
                    // 将起始标签入栈
                    stack.push(tag);
                }
            }
            i ++;
        }
        return stack.isEmpty();
    }
}
